Se rezolva cu dinamica. 

abcabbcabc -> cabbac

  a b c a b b c a b c
a 1 1 1 3 3 3 4 6 6 6
b 0 1 1 1 3 3 4 5 6 6
c 0 0 1 1 1 2 4 4 4 6
a 0 0 0 1 1 2 2 4 4 4
b 0 0 0 0 1 2 2 2 3 3
b 0 0 0 0 0 1 1 1 3 3
c 0 0 0 0 0 0 1 1 1 3
a 0 0 0 0 0 0 0 1 1 1
b 0 0 0 0 0 0 0 0 1 1
c 0 0 0 0 0 0 0 0 0 1

! O proprietate imp. a acestei matricii este ca Smp[i][j]>=vecinii din dr. , st. si diagonala jos (ex 6>5 , 6>4 , 6>4 pt. el. Smp[2][9] )

Consideram matricea Smp[][] si sirul initial a[]. Recursivitatea este urmatoarea:  

Val. init. Smp[i][i]=1;

Smp[i][j]=| Smp[i+1][j-1]+2 , daca a[i]==a[j]
          | 
	  | Maxim(Smp[i+1][j],Smp[i][j-1]) , daca a[i]!=a[j] && ( i==j || i>j )
		  
Ca sa aflam numarul de solutii avem nevoie sa construim matricea Smp[][] , iar apoi vom construi matricea nrp[][] dupa urm. recursivitate:

Val. init. nrp[i][i]=1 , nrp[i][i+1]=1;

- pt. a[i]==a[j] 
 1)  - Smp[i][j-1]!=Smp[i][j] && Smp[i+1][j]!=Smp[i][j] => nrp[i][j]=nrp[i-1][j-1]
 2)  - Smp[i][j-1]==Smp[i][j] && Smp[i+1][j]!=Smp[i][j] => nrp[i][j]=nrp[i-1][j-1]+nrp[i][j-1]
 3)  - Smp[i][j-1]!=Smp[i][j] && Smp[i+1][j]==Smp[i][j] => nrp[i][j]=nrp[i-1][j-1]+nrp[i+1][j]
- pt. a[i]!=a[j]
 4)  - Smp[i][j-1]==Smp[i][j] && Smp[i+1][j]!=Smp[i][j] && Smp[i-1][j-1]!=Smp[i][j] => nrp[i][j]=nrp[i][j-1]
 5)  - Smp[i][j-1]!=Smp[i][j] && Smp[i+1][j]==Smp[i][j] && Smp[i-1][j-1]!=Smp[i][j] => nrp[i][j]=nrp[i+1][j]
 6)  - Smp[i][j-1]==Smp[i][j] && Smp[i+1][j]==Smp[i][j] && Smp[i-1][j-1]!=Smp[i][j] => nrp[i][j]=nrp[i+1][j]+nrp[i][j-1]
 7)  - Smp[i][j-1]==Smp[i][j] && Smp[i+1][j]==Smp[i][j] && Smp[i-1][j-1]==Smp[i][j] => nrp[i][j]=nrp[i+1][j]+nrp[i][j-1]-nrp[i-1][j-1]
 
 Pentru a genera o solutie ne vom folosi de prima dinamica , anume cea cu Smp[][] si vom parcurge matricea in jos cat timp avem valori egale , 
 si dupa la st pana vom intalni o valoare cu 2 mai mica pe diagonala st-jos. 
 
 Cand construim tot ce avem mai sus in primele 2 cazuri rez. e in coltul dr sus al matricei , iar in al 3-lea recursivitatea va incepe din acest colt.